words = ["abcw","baz","foo","bar","xtfn","abcdef"]
#先用迭代法求解一次

#比较两个数是否有相同元素：
def haveSameElem(word1,word2):
    for i in word1:
        for j in word2:
            if i==j:
                return False
    return True
#这种方法的时间复杂度是O（n^4），这方法是严重的不行
def maxProduct(words):
    res=0
    for i in range(len(words)-1):
        for j in range(i+1,len(words)):
            if haveSameElem(words[i],words[j]):
                if res<len(words[i])*len(words[j]):
                    res=len(words[i])*len(words[j])
    print(res)
#大佬方法
def maxProduct1(words):
    n=len(words)
    index=0
    masks=[0 for _ in range(n)]
    for s in words:
        m=0
        for i in range(len(s)):
            k=ord(s[i])-ord('a')
            m|=(1<<k)
        masks[index]=m
        index+=1
    ans=0
    for i in range(n-1):
        for j in range(i+1,n):
            if (masks[i] & masks[j])==0:
                #没有相同的位，表示没有相同的字母
                ans=max(ans,len(words[i])*len(words[j]))
    return ans

#大佬方法
def maxProduct2(words):
    masks=dict()
    for s in words:
        m=0
        for i in range(len(s)):
            k=ord(s[i])-ord('a')
            m|=(1<<k)
        if m not in masks:
            masks[m]=len(s)
        else:
            if len(s)>masks[m]:
                masks[m]=len(s)
    ans=0
    for key1 in masks:
        for key2 in masks:
            if key1&key2==0 and ans<masks[key1]*masks[key2]:
                ans=masks[key1]*masks[key2]
    return ans
print(maxProduct2(words))


